// Created by WXX on 2021/12/13 23:11
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        int n = arr.size();
        vector<int> f(n + 1);
        for (int i = 1; i <= n; i++)
            for (int j = 1, v = 0; j <= k && j <= i; j++) {
                v = max(v, arr[i - j + 1 - 1]);
                f[i] = max(f[i], f[i - j] + v * j);
            }
        return f[n];
    }
};

int main() {


    return 0;
}
